1class TrieNode:
2    def __init__(self):
3        self.children: Dict[str, TrieNode] = {}
4        self.is_end_of_word: bool = False
5        self.frequency: int = 0
6
7    def get_children(self) -> Dict[str, TrieNode]:
8        return self.children
9
10    def is_end_of_word_check(self) -> bool:
11        return self.is_end_of_word
12
13    def set_end_of_word(self, end_of_word: bool):
14        self.is_end_of_word = end_of_word
15
16    def get_frequency(self) -> int:
17        return self.frequency
18
19    def increment_frequency(self):
20        self.frequency += 1

1class Suggestion:
2    def __init__(self, word: str, weight: int):
3        self.word = word
4        self.weight = weight
5
6    def get_word(self) -> str:
7        return self.word
8
9    def get_weight(self) -> int:
10        return self.weight

1class Trie:
2    def __init__(self):
3        self.root = TrieNode()
4
5    def insert(self, word: str):
6        current = self.root
7        for ch in word:
8            if ch not in current.get_children():
9                current.get_children()[ch] = TrieNode()
10            current = current.get_children()[ch]
11        current.set_end_of_word(True)
12        current.increment_frequency()
13
14    def search_prefix(self, prefix: str) -> Optional[TrieNode]:
15        current = self.root
16        for ch in prefix:
17            node = current.get_children().get(ch)
18            if node is None:
19                return None
20            current = node
21        return current
22
23    def collect_suggestions(self, start_node: TrieNode, prefix: str) -> List[Suggestion]:
24        suggestions = []
25        self._collect(start_node, prefix, suggestions)
26        return suggestions
27
28    def _collect(self, node: TrieNode, current_prefix: str, suggestions: List[Suggestion]):
29        if node.is_end_of_word_check():
30            suggestions.append(Suggestion(current_prefix, node.get_frequency()))
31
32        for ch in node.get_children().keys():
33            self._collect(node.get_children()[ch], current_prefix + ch, suggestions)

1class RankingStrategy(ABC):
2    @abstractmethod
3    def rank(self, suggestions: List[Suggestion]) -> List[Suggestion]:
4        pass
5
6class AlphabeticalRanking(RankingStrategy):
7    def rank(self, suggestions: List[Suggestion]) -> List[Suggestion]:
8        return sorted(suggestions, key=lambda s: s.get_word())
9
10class FrequencyBasedRanking(RankingStrategy):
11    def rank(self, suggestions: List[Suggestion]) -> List[Suggestion]:
12        return sorted(suggestions, key=lambda s: s.get_weight(), reverse=True)

1class AutocompleteSystem:
2    def __init__(self, ranking_strategy: RankingStrategy, max_suggestions: int):
3        self.trie = Trie()
4        self.ranking_strategy = ranking_strategy
5        self.max_suggestions = max_suggestions
6
7    def add_word(self, word: str):
8        self.trie.insert(word.lower())
9
10    def add_words(self, words: List[str]):
11        for word in words:
12            self.add_word(word)
13
14    def get_suggestions(self, prefix: str) -> List[str]:
15        prefix_node = self.trie.search_prefix(prefix.lower())
16        if prefix_node is None:
17            return []
18
19        raw_suggestions = self.trie.collect_suggestions(prefix_node, prefix.lower())
20        ranked_suggestions = self.ranking_strategy.rank(raw_suggestions)
21
22        return [s.get_word() for s in ranked_suggestions[:self.max_suggestions]]

1class AutocompleteSystemBuilder:
2    def __init__(self):
3        self.ranking_strategy = FrequencyBasedRanking()  # Default strategy
4        self.max_suggestions = 10  # Default limit
5
6    def with_ranking_strategy(self, strategy: RankingStrategy):
7        self.ranking_strategy = strategy
8        return self
9
10    def with_max_suggestions(self, max_suggestions: int):
11        self.max_suggestions = max_suggestions
12        return self
13
14    def build(self) -> AutocompleteSystem:
15        return AutocompleteSystem(self.ranking_strategy, self.max_suggestions)

1def main():
2    print("----------- SCENARIO 1: Frequency-based Ranking -----------")
3
4    # 1. Build the system with the default frequency-based strategy
5    system_by_frequency = (AutocompleteSystemBuilder()
6                          .with_max_suggestions(5)
7                          .with_ranking_strategy(FrequencyBasedRanking())
8                          .build())
9
10    # 2. Feed data into the system
11    # 'canada' is added most frequently, followed by 'car'
12    dictionary = [
13        "car", "cat", "cart", "cartoon", "canada", "candy",
14        "car", "canada", "canada", "car", "canada", "canopy", "captain"
15    ]
16    system_by_frequency.add_words(dictionary)
17
18    # 3. Get suggestions for a prefix
19    prefix1 = "ca"
20    suggestions1 = system_by_frequency.get_suggestions(prefix1)
21    print(f"Suggestions for '{prefix1}': {suggestions1}")
22
23    prefix2 = "car"
24    suggestions2 = system_by_frequency.get_suggestions(prefix2)
25    print(f"Suggestions for '{prefix2}': {suggestions2}")
26
27    print("\n----------- SCENARIO 2: Alphabetical Ranking -----------")
28
29    # 1. Build a new system with the alphabetical strategy
30    system_alphabetical = (AutocompleteSystemBuilder()
31                          .with_ranking_strategy(AlphabeticalRanking())
32                          .build())
33
34    # 2. Feed the same data
35    system_alphabetical.add_words(dictionary)
36
37    # 3. Get suggestions for the same prefix
38    suggestions3 = system_alphabetical.get_suggestions(prefix1)
39    print(f"Suggestions for '{prefix1}' (alphabetical): {suggestions3}")
40
41
42if __name__ == "__main__":
43    main()